//
// Created by yangchao on 2022/4/25.
// 20. 有效的括号: https://leetcode-cn.com/problems/valid-parentheses/
//
#include <string>
#include <stack>
#include <map>
using namespace std;

class IsValid {
public:
    bool isValid(string s) {
        if (s.size() % 2 == 1) return false;
        stack<char> st;
        map<char,char> bracket = {{'(',')'},{'[',']'},{'{','}'}};
        for (char ch: s) {
            if (ch == '(' || ch == '[' || ch == '{') {
                st.push(ch);
            } else {
                if (st.empty() || ch != bracket.at(st.top())) return false;
                st.pop();
            }
        }
        return st.empty();
    }
};
